#include<iostream>
#include<vector>
using namespace std;
class solution
{
public:
	void QuickSort(vector<int>& nums, int left, int right)
	{
		if (left >= right) return;
		int key = left;
		int prev = left;
		int cur = left + 1;
		while (cur <= right)
		{
			if (nums[cur] < nums[key])
			{
				prev++;
				swap(nums[prev], nums[cur]);
				cur++;
			}
			cur++;
		}
		swap(nums[prev], nums[cur]);
		key = prev;
		QuickSort(nums, left, key - 1);
		QuickSort(nums, key + 1, right);
	}
};